Search results for "Steiner Tree Problem"

Recent mathematical approaches to reconstruct phylogenies: A chemosystematist's and botanist's view

1989

Some basic problems of mathematical phylogenetics are discussed. While algorithms regularly depend on the principle of parsimony, some features of phylogenesis interfere with that principle. Nonrandomness of the distribution of mutations as well as the inconstancy of the molecular clock in time and within a given sequence can bias the calculated relationships of closely related taxa. True comparability of sequences is difficult to establish, since this requires defining of homology of positions and of functions of amino acids as well. Parallelism and convergence can give rise to errors in establishing homology. Furthermore, they are difficult to be integrated into a consistent mathematical …

Using a TSP heuristic for routing order pickers in warehouses

2010

In this paper, we deal with the sequencing and routing problem of order pickers in conventional multi-parallel-aisle warehouse systems. For this NP-hard Steiner travelling salesman problem (TSP), exact algorithms only exist for warehouses with at most three cross aisles, while for other warehouse types literature provides a selection of dedicated construction heuristics. We evaluate to what extent reformulating and solving the problem as a classical TSP leads to performance improvements compared to existing dedicated heuristics. We report average savings in route distance of up to 47% when using the LKH (Lin-Kernighan-Helsgaun) TSP heuristic. Additionally, we examine if combining problem-sp…

Efficient Tree Construction for the Multicast Problem

1999

Optimal Resource Discovery Paths of Gnutella2

2008

This paper shows that the performance of peer-to-peer resource discovery algorithms is upper bounded by a k-Steiner minimum tree and proposes an algorithm locating near-optimal query paths for the peer-to-peer resource discovery problem. Global knowledge of the topology and the resources from the peer-to-peer network are required as an input to the algorithm. The algorithm provides an objective measure for defining how good local search algorithms are. The performance is evaluated in simulated peer-to-peer scenarios and in the measured Gnutella2 P2P network topology with four local search algorithms: breadth-first search, self-avoiding random walker, highest degree search and Dynamic Query …

Basic networks: Definition and applications

2009

7 pages, 4 figures, 1 table.-- PMID: 19490867 [PubMed]

An efficient distributed algorithm for generating and updating multicast trees

2006

As group applications are becoming widespread, efficient network utilization becomes a growing concern. Multicast transmission represents a necessary lower network service for the wide diffusion of new multimedia network applications. Multicast transmission may use network resources more efficiently than multiple point-to-point messages; however, creating optimal multicast trees (Steiner Tree Problem in networks) is prohibitively expensive. This paper proposes a distributed algorithm for the heuristic solution of the Steiner Tree Problem, allowing the construction of effective distribution trees using a coordination protocol among the network nodes. Furthermore, we propose a novel distribut…

A Grid Enabled Parallel Hybrid Genetic Algorithm for SPN

2004

This paper presents a combination of a parallel Genetic Algorithm (GA) and a local search methodology for the Steiner Problem in Networks (SPN). Several previous papers have proposed the adoption of GAs and others metaheuristics to solve the SPN demonstrating the validity of their approaches. This work differs from them for two main reasons: the dimension and the features of the networks adopted in the experiments and the aim from which it has been originated. The reason that aimed this work was namely to assess deterministic and computationally inexpensive algorithms which can be used in practical engineering applications, such as the multicast transmission in the Internet. The large dimen…

New Algorithms for Computing Phylogenetic Biodiversity

2014

A common problem that appears in many case studies in ecology is the following: given a rooted phylogenetic tree \(\mathcal{T}\) and a subset R of its leaf nodes, we want to compute the distance between the elements in R. A very popular distance measure that can be used for this reason is the Phylogenetic Diversity (PD), which is defined as the cost of the minimum weight Steiner tree in \(\mathcal{T}\) that spans the nodes in R. To analyse the value of the PD for a given set R it is important also to calculate the variance of this measure. However, the best algorithm known so far for computing the variance of the PD is inefficient; for any input tree \(\mathcal{T}\) that consists of n nodes…

On the Low-Dimensional Steiner Minimum Tree Problem in Hamming Metric

2011

It is known that the d-dimensional Steiner Minimum Tree Problem in Hamming metric is NP-complete if d is considered to be a part of the input. On the other hand, it was an open question whether the problem is also NP-complete in fixed dimensions. In this paper we answer this question by showing that the problem is NP-complete for any dimension strictly greater than 2. We also show that the Steiner ratio is 2 - 2/d for d ≥ 2. Using this result, we tailor the analysis of the so-called k-LCA approximation algorithm and show improved approximation guarantees for the special cases d = 3 and d = 4.

A Dynamic Distributed Algorithm for Multicast Path Setup

2005

In the past few years, there has been a considerable work on multicast route selection techniques, with the aim to design scalable protocols which can guarantee an efficient use of network resources. Steiner tree-based multicast algorithms produce optimal trees, but they are prohibitively expensive. For this reason, heuristic methods are generally employed. Conventional centralized Steiner heuristics provide effective solutions, but they are unpractical for large networks, since they require a complete knowledge of the network topology. In this paper, we propose a new distributed approach that is efficient and suitable for real network adoption. Performance evaluation indicates that it outp…